package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/14 19:40
 *
 *
 判断是否为平衡二叉树
 */

import java.util.HashMap;
import java.util.Map;

public class Main25 {
    class TreeNode{
        TreeNode left;
        TreeNode right;
        Integer val;
        TreeNode(Integer val){
            this.val=val;
        }
    }

    //做一个记忆化,如果每个点都要遍历高度复杂度太高了，只需遍历一遍保存即可
    HashMap<TreeNode,Integer> height=new HashMap<>();
    public int depth(TreeNode root){
        if(root==null)return 0;
        if(height.containsKey(root))return height.get(root);
            Integer h=Math.max(depth(root.left),depth(root.right))+1;
            height.put(root,h);
            return h;
    }
    //自顶向下判断
    public boolean judge(TreeNode root){
        if(root==null)return true;
        return Math.abs(height.get(root.left)-height.get(root.right))<=1
                &&judge(root.left)&&judge(root.right);
    }
    public boolean IsBalanced_Solution(TreeNode root) {
        depth(root);
        height.put(null,0);//防止空指针异常
        return judge(root);
    }


    //可以边计算高度的时候，自底向上判断，如果高度差超过了1就直接返回-1
    public int  getDepth(TreeNode root){
        if(root==null)return 0;
        int l=getDepth(root.left);
        if(l==-1)return -1;
        int r=getDepth(root.right);
        if(r==-1)return -1;

        int flag=Math.abs(l-r);
        if(flag>1)return -1;
        else{
            return Math.max(l,r)+1;
        }
    }

    public static void main(String[] args) {
        HashMap<TreeNode,Integer>map=new HashMap<>();
        map.put(null,0);
        for (Map.Entry<TreeNode,Integer> entry:map.entrySet()){
            System.out.println(entry.getKey().val+"--"+entry.getValue());
        }
        System.out.println(map.get(null));
    }
}
